package 合并K个升序链表;

public class Solution {
    public static void main(String[] args) {

        System.out.println(Integer.parseInt(String.valueOf(-1)));

        Solution solution = new Solution();

//        String input = "[1,4,5]o[1,3,4]o[2,6]";
        String input = "[-1,5,11]o[6,10]";
        String[] split = input.split("o");

        ListNode[] lists = new ListNode[split.length];
        int index = 0;
        for (String str : split) {

            String[] split1 = str.substring(1,str.length()-1).split(",");
            ListNode node = new ListNode(Integer.parseInt(String.valueOf(split1[0])));
            ListNode pre = node;

            for (int i = 1; i < split1.length; i++) {
                ListNode temp = new ListNode(Integer.parseInt(split1[i]));
                pre.next = temp;
                pre = temp;
            }

            lists[index++] = node;
        }

        ListNode listNode = solution.mergeKLists(lists);

    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        if (lists.length < 2) {
            return lists[0];
        }

        int num = findMin(-10001, lists);
        if(num == -10001){
            return null;
        }
        ListNode firstNode = new ListNode(num);

        ListNode pre = firstNode;
        num = findMin(num, lists);
        while(num != -10001){
            ListNode temp = new ListNode(num);

            pre.next = temp;
            pre = temp;
            num = findMin(num, lists);
            System.out.println(num);
        }


        return firstNode;
    }

    public int findMin(int num, ListNode[] lists) {
        int min = num;
        int min2 = -10001;
        int index = -1;

        boolean exist = false;
        for (int i = 0; i < lists.length; i++) {
            ListNode list = lists[i];
            if(list == null){
                continue;
            }
            if (list.val == min) {
                list = list.next;
                lists[i] = list;
                return min;
            } else  {
                if(min2 == -10001){
                    min2 = list.val;
                    index = i;
                }
                else if(list.val < min2) {
                    min2 = list.val;
                    index = i;
                }
                exist = true;
            }
        }

        if(exist){
            num = lists[index].val;
            lists[index] = lists[index].next;
            return num;
        }
        else{
            return -10001;
        }


    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
